/*
 * @Author: liusheng
 * @Date: 2022-06-07 10:45:28
 * @LastEditors: liusheng
 * @LastEditTime: 2022-06-07 11:00:40
 * @Description: 剑指 Offer II 075. 数组相对排序
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 剑指 Offer II 075. 数组相对排序
给定两个数组，arr1 和 arr2，

arr2 中的元素各不相同
arr2 中的每个元素都出现在 arr1 中
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

 

示例：

输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]
 

提示：

1 <= arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
arr2 中的元素 arr2[i] 各不相同
arr2 中的每个元素 arr2[i] 都出现在 arr1 中
 

注意：本题与主站 1122 题相同：https://leetcode-cn.com/problems/relative-sort-array/ 

通过次数13,424   提交次数18,982
 */

#include "header.h"
/*
use-define compare solution
*/
class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        std::unordered_map<int,int> valWeight;
        int maxWeight = arr2.size();
        for (int i = 0; i < arr2.size(); ++i)
        {
            valWeight[arr2[i]] = maxWeight--;
        }

        auto weightGrtCmp = [&valWeight](const int a,const int b)
        {
            auto hasA = valWeight.count(a);
            auto hasB = valWeight.count(b);
            if (hasA && hasB)
            {
                return valWeight[a] > valWeight[b];
            }
            else if(hasA)
            {
                return true;
            }
            else if(hasB)
            {
                return false;
            }
            else 
            {
                return a < b;
            }
        };

        std::sort(arr1.begin(),arr1.end(),weightGrtCmp);

        return arr1;
    }
};

/*
Radix sort solution
*/
class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        auto maxV = max_element(arr1.begin(),arr1.end());
        vector<int> frequence(*maxV + 1,0);
        for (auto num : arr1)
        {
            ++frequence[num];
        }

        vector<int> result;
        for (auto num : arr2)
        {
            while (frequence[num])
            {
                result.push_back(num);
                --frequence[num];
            }
        }

        for (int i = 0; i <= *maxV; ++i)
        {
            while (frequence[i]--)
            {
                result.push_back(i);
            }
        }

        return result;
    }
};
